package com.zwj.interview.动态规划;

/**
 * 题目：给定一个非空的正整数数组nums和一个目标值t，数组中的所有数字都是唯一的，
 * 请计算数字之和等于t的所有排列的数目。数组中的数字可以在排列中出现任意次。
 * 例如，输入数组[1，2，3]，目标值t为3，那么总共有4个组合的数字之和等于3，
 * 它们分别为{1，1，1}、{1，2}、{2，1}及{3}
 */
public class 和等于目标值的子数组排列数 {

    /**
     * 分析：
     * 如果将数组中的每个数字看成硬币的面额，而将目标值t看成总额，那么这个问题和面试题103是非常类似的。
     * 可以用类似的思路来推导状态转移方程
     * <p>
     * 用f（i）表示和为i的排列的数目。为了得到和为i的排列，
     * 有如下选择：
     * 在和为i-nums[0]的排列中添加标号为0的数字，此时f（i）等于f（i-nums[0]）；
     * 在和为i-nums[1]的排列中添加标号为1的数字，此时f（i）等于f（i-nums[1]）。
     * 以此类推，在和为i-nums[n-1]的排列中添加标号为n-1的数字（n为数组的长度），此时f（i）等于f（i-nums[n-1]）。
     * 因为目标是求出所有和为i的排列的数目，所以将上述所有情况全部累加起来。该状态转移方程可以表示为
     * f (i)=∑f (i-nums[j])(nums[j]≤i)
     * <p>
     * 由于只有一个空排列的数字之和等于0，因此f（0）等于1
     * dp[i]表示和为i的排列数
     */

    public int permutationSum(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; ++i) {
            //在这里循环是因为数字可以重复
            for (int num : nums) {
                if (i >= num) {
                    //选择了num，那么就需要在总和上
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }




}
